  // 查找一个数
  const nums = [-1,0,3,5,9,12], target = 5;
  function binarySearch(nums, target) {
    let left = 0;right = nums.length - 1;
    while(left <= right) {
      let mid = parseInt(left + (right - left) / 2);
      if (nums[mid] == target) {
        return mid;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else if (nums[mid] > target) {
        right = mid - 1;
      }
    }

    return -1;
  }

  console.log(binarySearch(nums, target));


  // 二分查找，查找第一个存在的数
  function binarySearchFirst(nums, target) {
    let left = 0, right = nums.length - 1;
    while(left <= right) {
      let mid = parseInt(left + (right - left) / 2);
      if (nums[mid] == target) {
        right = mid - 1;
      } else if(nums[mid] < target){
        left  = mid + 1
      } else if(nums[mid] > target) {
        right = mid - 1
      }
    }

    if (left >= nums.length || nums[left] != target) {
      return -1;
    }

    return left;
  }

  const nums2 = [1,2,2,2,3], target2 = 2;

  console.log(binarySearchFirst(nums2, target2))
  // 二分查找，查找最后一个存在的数
  function binarySearchLast(nums, target) {
    let left = 0, right = nums.length - 1;
    while(left <= right) {
      let mid = parseInt(left + (right - left) / 2);
      if (nums[mid] == target) {
        left = mid + 1;
      } else if(nums[mid] < target){
        left  = mid + 1
      } else if(nums[mid] > target) {
        right = mid - 1
      }
    }

    if (right < 0|| nums[right] != target) {
      return -1;
    }

    return right;
  }

  console.log(binarySearchLast(nums2, target2));

// 搜索旋转排序数组
const nums3 = [4,5,6,7,0,1,2], target3 = 0
function search(nums, target) {
  let left = 0, right = nums.length - 1;
  while(left <= right) {
    let mid = parseInt(left + (right - left) / 2);
    if (nums[mid] == target) {
      return mid;
    } 
    if(nums[0] <= nums[mid]){
      if (target >= nums[0] && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else{
      if (target > nums[mid] && target <= nums[nums.length - 1]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return -1;
}

console.log(search(nums3, target3))

function searchRange(nums, target) {
  let left = 0, right = nums.length - 1;
  let ans = [];
  while(left <= right) {
    let mid = parseInt(left + (right - left) / 2);
    if (nums[mid] == target) {
      right = mid - 1;
      ans.unshift(mid);
    } else if(nums[mid] < target){
      left  = mid + 1
    } else if(nums[mid] > target) {
      right = mid - 1
    }
  }

  if (left >= nums.length || nums[left] != target) {
    return -1;
  }

  return ans;
}
let nums4 = [5,7,7,8,8,10], target4 = 8;
console.log(searchRange(nums4, target4), 'kkkk');
